UVa/11514 - Batman/batman.cpp

   1 //CODIGO EQUIPO FACTOR COMUN
   2
   3
   4 #include <string>
   5 #include <vector>
   6 #include <iostream>
   7 #include <sstream>
   8 #include <algorithm>
   9
  10 using namespace std;
  11
  12 struct power {
  13   string name;
  14   int atk;
  15   int e;
  16 };
  17
  18 struct vil {
  19     string name;
  20     int def;
  21     vector<string> pweak;
  22 };
  23 bool com[1005][1005];
  24 long long dp[1005][1005];
  25 int main() {
  26   //assert(freopen("batman.in", "r", stdin) != NULL);
  27     int p,v,e;
  28     cin >> p >> v >> e;
  29     while(p!=0 && v!=0 && e!=0) {
  30         vector<power> powers(p);
  31         vector<vil> vils(v);
  32         for(int i =0; i<p;++i) {
  33             power pp;
  34             cin >> pp.name >> pp.atk >> pp.e;
  35             powers[i] = pp;
  36         }
  37         for(int i =0; i<v; ++i) {
  38             vil vv;
  39             string pw;
  40             cin >> vv.name >> vv.def >> pw;
  41             for(int k =0; k<pw.size(); ++k) {
  42                 if(pw[k]==',') pw[k] = ' ';
  43             }
  44             stringstream ss(pw);
  45             while(ss>>pw) vv.pweak.push_back(pw);
  46             sort(vv.pweak.begin(),vv.pweak.end());
  47             vils[i] = vv;
  48         }
  49
  50         //bool com[p+1][v+1];
  51         memset(com,0,sizeof com);
  52         for(int i=0;i<p;++i) {
  53             for(int j =0; j<v; ++j) {
  54                 com[i+1][j+1] = powers[i].atk>=vils[j].def && binary_search(vils[j].pweak.begin(),vils[j].pweak.end(),powers[i].name);
  55             }
  56         }
  57         //long long dp[p+1][v+1];
  58         for(int j = 1; j<=v; ++j) {
  59             dp[0][j] = INT_MAX;
  60         }
  61         for(int i = 0; i<=p; ++i ) {
  62             dp[i][0] = 0;
  63         }
  64         for(int i=1; i<=p; ++i) {
  65             for(int j =1; j<=v; ++j) {
  66                 dp[i][j] = dp[i-1][j];
  67                 if(com[i][j]) dp[i][j] = min(dp[i][j],dp[i-1][j-1]+powers[i-1].e);
  68             }
  69         }
  70         if(dp[p][v]<=e) cout << "Yes" << endl;
  71         else cout << "No" << endl;
  72         /*for(int i=0;i<p;++i) {
  73             for(int j =0; j<v; ++j) {
  74                 cout << com[i+1][j+1];
  75             }
  76             cout << endl;
  77         }*/
  78         /*for(int i=1; i<=p; ++i) {
  79             for(int j =1; j<=v; ++j) {
  80                 cout << dp[i][j] << " ";
  81             }
  82             cout << endl;
  83         }*/
  84         cin >> p >> v >> e;
  85     }
  86     return 0;
  87 }